package com.algorithm.example.tree;

import java.util.LinkedList;

/**
 * <p>
 * 二叉搜索树
 * </p>
 *
 * @author lzt
 * @version 1.0
 * @since 2024/2/5 13:00
 */
public class BSTNode1 {

    BSTNode root;

    public static class BSTNode {
        /**
         * 若希望任意类型作为key,则后续可以设计为Comparable接口
         */
        int key;
        Object value;
        BSTNode left;
        BSTNode right;

        public BSTNode(int key) {
            this.key = key;
        }

        public BSTNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        public BSTNode(int key, Object value, BSTNode left, BSTNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return "\nBSTNode{" +
                    "key=" + key +
                    ", value=" + value +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }


    /**
     * 查找关键字对应的值
     *
     * @param key - 关键字
     * @return - 关键字对应的值
     */
    public Object get(int key) {
        BSTNode p = root;
        while (p != null) {
            if (key < p.key) {
                p = p.left;
            } else if (key > p.key) {
                p = p.right;
            } else {
                return p;
            }
        }
        return null;
    }

    /**
     * 存储关键字和对应值
     *
     * @param key   - 关键子
     * @param value - 值
     */
    public void put(int key, Object value) {
        BSTNode p = root;
        BSTNode p1 = null;
        if (root == null) {
            root = new BSTNode(key, value);
        } else {
            while (p != null) {
                p1 = p;
                if (key > p.key) {
                    p = p.right;
                } else if (key < p.key) {
                    p = p.left;
                } else {
                    p.value = value;
                    return;
                }
            }
            if (key > p1.key) {
                p1.right = new BSTNode(key, value);
            } else {
                p1.left = new BSTNode(key, value);
            }
        }
    }

    /**
     * 查找最小关键字对应的值
     *
     * @return - 返回对应的值
     */
    public Object min() {
        return min(root);
    }

    private Object min(BSTNode root) {
        if (root == null) {
            return null;
        }
        BSTNode p = root;
        while (p.left != null) {
            p = p.left;
        }
        return p;
    }

    /**
     * 查找最大关键字的对应值
     *
     * @return - 关键字对应值
     */
    public Object max() {
        return max(root);
    }

    private Object max(BSTNode root) {
        if (root == null) {
            return null;
        }
        BSTNode p = root;
        while (p.right != null) {
            p = p.right;
        }
        return p;
    }

    /**
     * 查找关键字的前任值
     *
     * @param key - 关键字
     * @return - 前任值
     */
    public Object predecessor(int key) {
        BSTNode p = root;
        BSTNode ancestor = null;
        while (p != null) {
            if (p.key < key) {
                ancestor = p;
                p = p.right;
            } else if (p.key > key) {
                p = p.left;
            } else {
                break;
            }
        }
        // 1.找不到
        if (p == null) {
            return null;
        }

        // 2.节点有左子树
        if (p.left != null) {
            return max(p.left);
        }

        // 3.没有左子树，找自左而来的祖先
        return ancestor == null ? null : ancestor.value;
    }

    /**
     * 查找关键字的后任值
     *
     * @param key - 关键字
     * @return - 后任值
     */
    public Object successor(int key) {
        BSTNode p = root;
        BSTNode ancestor = null;
        while (p != null) {
            if (p.key < key) {
                p = p.right;
            } else if (p.key > key) {
                ancestor = p;
                p = p.left;
            } else {
                break;
            }
        }

        // 1.没有
        if (p == null) {
            return null;
        }
        // 2. 有右树
        if (p.right != null) {
            return min(p.right);
        }
        // 3.找到自
        return ancestor == null ? null : ancestor.value;
    }

    /**
     * 删除树中的节点
     *
     * @param key - 索引
     * @return - 返回删除的值
     */
    public Object remove(int key) {
        BSTNode p = root;
        BSTNode parent = null;
        while (p != null) {
            if (p.key > key) {
                parent = p;
                p = p.left;
            } else if (p.key < key) {
                parent = p;
                p = p.right;
            } else {
                break;
            }
        }

        if (p == null) {
            return null;
        }
        // 1.左孩子
        if (p.left != null && p.right == null) {
            shift(parent, p, p.left);
            p.left = p.right = null;
        }

        // 2.右孩子
        if (p.left == null && p.right != null) {
            shift(parent, p, p.right);
            p.left = p.right = null;
        }

        // 3.两个孩子
        if (p.right != null) {
            // 被删除节点找后续
            BSTNode s = p.right;
            BSTNode parent1 = p; //后续父亲
            while (s.left != null) {
                parent1 = s;
                s = s.left;
            }

            // 删除和后继不相邻，处理后继的后事
            if (parent1 != p) {
                shift(parent1, s, s.right); // 不可有左孩子
                s.right = p.right;
            }
            // 后继取代被删除节点
            shift(parent, p, s);
            s.left = p.left;
        }

        return p;
    }

    /**
     * 托孤方法
     *
     * @param parent  被删除节点的父亲
     * @param deleted 被删除节点
     * @param child   被顶上去的节点
     */
    private void shift(BSTNode parent, BSTNode deleted, BSTNode child) {
        if (parent == null) {
            root = child;
            return;
        }
        if (deleted == parent.left) {
            parent.left = child;
        } else {
            parent.right = child;
        }
    }

    /**
     * 中序遍历
     */
    public void Order() {
        Order(root);
    }

    public void Order(BSTNode root) {
        if (root == null) {
            return;
        }
        Order(root.right);
        System.out.print(root.key + "\t");
        Order(root.left);

    }

    /**
     * 前序遍历
     */
    public void preOrder() {
        if (root == null) {
            return;
        }
        LinkedList<BSTNode> bstNodes = new LinkedList<>();
        BSTNode p = root;
        while (p != null || !bstNodes.isEmpty()) {
            if (p != null) {
                bstNodes.push(p);
                System.out.print(p.key + "\t");
                p = p.left;
            } else {
                BSTNode pop = bstNodes.pop();
                p = pop.right;
            }

        }
    }

    @Override
    public String toString() {
        return "BSTNode1{" +
                "root=" + root +
                '}';
    }
}
